package com.test.demo;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by jl on 2019/6/28 0028
 * 计算树的宽度
 */
public class BinaryTreeWidth {
    private static final HashMap<Integer, LevelCache> LEVEL_HOLDER = new HashMap<>();

    public static void main(String[] args) {
        Node root = getTreeRootNode();
        int w = calcWidth(root);
        System.out.println("width:" + w);
    }

    private static int calcWidth(Node root) {
        parse(root, 1);
        int maxWidth = 0;
        for (Map.Entry<Integer, LevelCache> entry : LEVEL_HOLDER.entrySet()) {
            int width = entry.getValue().width();
            System.out.println(String.format("level:%d,width:%d", entry.getKey(), width));
            if (width > maxWidth) {
                maxWidth = width;
            }
        }
        return maxWidth;
    }

    private static void parse(Node node, int level) {
        System.out.println("level:" + level + ", " + (node != null ? node.data : "node null"));
        LEVEL_HOLDER.putIfAbsent(level, initLevelCache());
        LevelCache levelCache = LEVEL_HOLDER.get(level);
        levelCache.count++;
        if (node != null) {
            if (levelCache.leftNodeSite == 0) {
                levelCache.leftNodeSite = levelCache.count;
            }
            levelCache.rightNodeSite = levelCache.count;
            parse(node.left, level + 1);
            parse(node.right, level + 1);
        }
    }

    private static LevelCache initLevelCache() {
        return new LevelCache();
    }

    private static Node getTreeRootNode() {
        Node root = new Node("1");
        root.left = new Node("2");
        root.right = new Node("3");
        root.left.left = new Node("4");
        root.right.left = new Node("5");
        root.right.left.left = new Node("6");
        root.right.left.right = new Node("7");
        return root;
    }

    private static class Node {
        Node left;
        Node right;
        Object data;

        Node(Object data) {
            this.data = data;
        }
    }

    private static class LevelCache {
        int count;

        int leftNodeSite;
        int rightNodeSite;

        int width() {
            return leftNodeSite != 0 ? rightNodeSite - leftNodeSite + 1 : 0;
        }
    }
}
